//给定一个未排序的整数数组，找出最长连续序列的长度。 
//
// 要求算法的时间复杂度为 O(n)。 
//
// 示例: 
//
// 输入: [100, 4, 200, 1, 3, 2]
//输出: 4
//解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。 
// Related Topics 并查集 数组


package leetcode.d_100_199;

import java.util.HashSet;
import java.util.Set;

//Java：最长连续序列
public class P128LongestConsecutiveSequence{
    public static void main(String[] args) {
        Solution solution = new P128LongestConsecutiveSequence().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
//    class Solution {
//        public int longestConsecutive(int[] nums) {
//            int max = 0;
//            for (int i = 0; i < nums.length; i++) {
//                int curmax = 1;
//                int curNum = nums[i];
//                while (arrayContains(nums, curNum + 1)){
//                    curNum += 1;
//                    curmax++;
//                }
//                max = Math.max(max, curmax);
//            }
//            return max;
//        }
//
//        public boolean arrayContains(int[] nums, int temp) {
//            for (int i = 0; i < nums.length; i++) {
//                if (nums[i] == temp){
//                    return true;
//                }
//            }
//            return false;
//        }
//    }

//    class Solution {
//        public int longestConsecutive(int[] nums) {
//            if (nums.length == 0){
//                return 0;
//            }
//            Arrays.sort(nums);
//
//            int max = 1;
//            int curMax = 1;
//
//            for (int i = 1; i < nums.length; i++) {
//                if (nums[i] == nums[i-1]){
//                    continue;
//                }
//                if (nums[i] == nums[i-1] + 1){
//                    curMax++;
//                }else {
//                    max = Math.max(curMax, max);
//                    curMax = 1;
//                }
//            }
//            return Math.max(curMax, max);
//        }
//    }


    class Solution {
        public int longestConsecutive(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for(int num : nums){
                set.add(num);
            }

            int max = 0;
            for(int num : set){
                int curNum = num;
                int curMax = 1;
                if (!set.contains(curNum-1)){
                    while (set.contains(curNum + 1)){
                        curMax++;
                        curNum++;
                    }
                    max = Math.max(curMax, max);
                }
            }
            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}